package com.luoha.random;

import java.util.Date;
import java.util.Random;

/*
 * 随即排列数组，给定一个数组，随即排列其中的元素，目前主要有两种方法
 */
public class RandomSort {
	public static void main(String args[]) {
		int data[] = new int[] { 1, 42, 51, 62, 8, 94, 23, 13, 40, 5 };
		// int p[]=getRandom(1,-8,100);
		// show(p);
		show(data);
		permuteBySort(data);
		show(data);
		randomizeInPlace(data);
		show(data);
		System.exit(0);
	}

	/*
	 * 随机排列数组,使用优先级方式,每个数组元素A[i] 对应一个优先级P[i]， 然后依据优先级对数组进行排序
	 */
	public static void permuteBySort(int[] data) {
		int len = data.length;
		int len3 = len * len * len;
		int P[] = getRandom(1, len3, len);
		// 冒泡排序
		for (int i = len - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (P[j] > P[j + 1]) {
					int temp = data[j];
					data[j] = data[j + 1];
					data[j + 1] = temp;
					temp = P[j];
					P[j] = P[j + 1];
					P[j + 1] = temp;
				}
			}
		}
	}

	/*
	 * 元素A[i]是从 元素A[i]到A[n]中随机选取的
	 */
	public static void randomizeInPlace(int[] data) {
		Date dt = new Date();
		Random random = new Random(dt.getSeconds());
		int len = data.length;
		for (int i = 0; i < len; i++) {
			int pos = (int) (random.nextDouble() * (len - i + 1) + i) - 1;
			int temp = data[i];
			data[i] = data[pos];
			data[pos] = temp;
		}
	}

	/*
	 * 获得在a到b之间的n个随机数
	 */
	private static int[] getRandom(int a, int b, int n) {
		if (a > b) {
			int temp = a;
			a = b;
			b = temp;
		}
		Date dt = new Date();
		Random random = new Random(dt.getSeconds());
		int res[] = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = (int) (random.nextDouble() * (Math.abs(b - a) + 1)) + a;
		}
		return res;
	}

	private static void show(int[] data) {
		System.out.println("========================");
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.println();
		System.out.println("========================");
	}
}